COMP124

Semaphores

Semaphores are like tokens to access a critical region, where while it's being used, other processes/threads cannot access the critical region

Semaphore Notation

The semaphore mechanism provides two operations

• wait() and signal()
• Sometimes called P and V, test and inc, or up and down
• As they have two states, semaphores can be implemented as a Boolean variable
• Java uses different names for its semaphore methods but they do the same thing

A thread must call wait() before it enters a critical region

• This will block if the region (semaphore) is in use by another thread
• Otherwise the thread obtains the lock and can enter the critical region
  The thread must call signal() just before it exits the critical region
• This releases (unlocks) the semaphore
• Any other blocked threads will be notified that the region is now safe to enter (only one thread will be successful if there are multiple threads waiting)

The Producer-Consumer Problem

This problem is a good way to illustrate how semaphores work

• The producer and consumer are separate threads with different roles
• Both the producer and consumer require access to a shared resource
• There could be multiple producers and/or consumers accessing the same resource
  For example...
• A secretary writes a letter (producer)
• They put the letter into a tray (shared resource)
• A manager takes the letter from the tray to sign it (consumer)
  In programming terms...
• Threads are usually consumers or producers of some resource
• The resource is a shared variable or object represented by a class (in Java)

Buffer

The problem and solution can be modelled as two threads trying to access a buffer

• Producer cannot insert if the buffer is full
• Consumer cannot remove if the buffer is empty
• Buffer cannot be accessed by multiple producers and consumers at the same time

Consider:

class Buffer {
	private int store;
	public void insert(int item) {
		store = item;
	}
	public int remove() {
		return store;
	}
}

Producer and Consumer

Consider:

class Producer extends Thread {
	private Buffer buff;
	public Producer(Buffer b) {
		buff = b;
	}
	public void run() {
		int m;
		...
		buff.insert(m);
		...
	}
}

The consumer object looks the same but it removes from the buffer instead
n = buff.remove();

None of this has protection for constraints mentioned

• Producer doesn't check to see if the buffer is full
• Consumer doesn't check to see if the buffer is empty
• Buffer is not protected from being used by both threads at the same time

Semaphore

class Buffer  {
	private int store;
	private volatile boolean empty = true;
	public void insert(int item) {
		while(!empty); // simulating wait()
		store = item;
		empty = false;  // simulating signal()
	}
	public int remove() {
		while(empty);   // simulating wait()
		empty = true;  // simulating signal()
		return store;
	}
}

The volatile keyword prevents variables from being cached (always uses latest value)
This version prevents threads trying to insert if buffer is full (or remove if buffer is empty)

Spinlock

Before inserting anything, the producer waits for the buffer to be empty

• while(!empty);
• empty = false;
  Before removing anything, the consumer waits for the buffer to be full
• while(empty);
• empty = true;
  These seemingly infinite loops may terminate as the status variable is shared between multiple threads, and another thread may update its value

This concept is known as spinlock or busy waiting

• Happens when you have an empty loop
• It works well, but is inefficient because it wastes CPU cycles
• Should only be used when expected wait time is very short

A blocked thread gets time on the CPU to effectively do nothing (go around an empty while loop)

Yielding

It could be more efficient for the waiting thread to give up control of the CPU

public void insert(int item) {
	while(!empty) {
		Thread.yield();
	}
	store = item;
	empty = false;
}

The yield() method tells JVM that the thread is willing to block

• Behaviour depends on JVM implementation
• JVM might ignore the request, so still need to put it within a spinlock
• The request is non-deterministic (might behave differently on different occasions)

Here, you would also use the synchronized keyword

public synchronized void insert(int item)

This ensures that only one thread can be inside this subroutine at a time, so no two producers are inserting to the buffer at the same time
If a thread tries to call a synchronized method, but another thread is already inside that method, the new thread calling the method will have to wait

Java Object Locks

Every Java object has a lock associated with it

• Locks are not shared across multiple instances of the same class
• Each object instance has its own lock that works independently of other instances
  The synchronized keyword declares methods that contain critical regions
• When a thread calls a synchronized method, it gets exclusive control of the lock
• Other calls to the object's synchronized methods must wait (block) in an entry set
• Note that non-synchronized methods can still be called without issues
  When the thread with the lock exits the synchronized method, the lock is released
• JVM will select an arbitrary thread from the entry set
• That thread will be able to call the synchronized method it was waiting for

Wait and Notify

Java provides methods to implement semaphores

public synchronized void insert(int item) {
	while(!empty) {
		try {
			wait();
		} catch(InterruptedException e) {}
	}
	store = item;
	empty = false;
	notify();
}

These methods will always work regardless of the JVM or platform, unlike yield which could be ignored by JVM

Entry and Wait Sets

The wait() call suspends current thread and moves it to the wait set
The notify() call moves an arbitrary thread from the wait set to the entry set (The choice of thread depends on the JVM implementation)
![[Pasted image 20250519074040.png]]
Can also call notifyAll() to allow all threads in the wait set to compete for the chance to resume

Java Semaphore Class

Java provides a Semaphore class that can be used

import java.util.concurrent.*;

Specify how many permits the semaphore allows (counting semaphore)

Semaphore sem = new Semaphore(1);

When the acquire() method is called:

• If the counter is 0, the thread will block (added to a wait queue)
• If the counter is greater than 0, counter is decreased and the thread can continue
  When the release() method is called:
• The counter is increased
• The first blocked thread in the wait queue can acquire the permit
  Testing and setting the counter must be atomic operations to avoid race conditions

class Buferr {
	private int store;
	private Semaphore sem = new Semaphore(1);
	public synchronized void insert(int item) {
		try { sem.acquire(); } catch(InterruptedException e) {}
		store = item;
		sem.release();
	}
	public synchronized int remove() {
		try { sem.acquire(); } catch(InterruptedException e) {}
		int item = store;
		sem.release();
		return item;
	}
}

This is the proper way to implement semaphores in Java